package _06_动态规划;

import java.util.ArrayList;
import java.util.List;

public class _300_最长递增子序列 {

    public static void main(String[] args) {

        _300_最长递增子序列 v = new _300_最长递增子序列();
        int[] ins = new int[]{0,1,0,3,2,3};
        System.out.println(v.lengthOfLIS(ins));

    }

    public int lengthOfLIS(int[] nums) {
        int max = 1;
        List<Integer> results = new ArrayList<>();
        results.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            int insertIndex = binarySearch(results, nums[i]);
            if (insertIndex == 0) {
                // 记录升序列表的最大值
                max = Math.max(results.size(), max);
                // 清空数组元素
                results.clear();
                results.add(nums[i]);
            } else {
                if (insertIndex >= results.size()) {
                    results.add(insertIndex, nums[i]);
                } else {
                    results.set(insertIndex, nums[i]);
                }
            }
        }
        return Math.max(max, results.size());
    }

    // 二分查找当前集合中的元素
    public int binarySearch(List<Integer> nums, int value) {
        // 找到元素第一个小于等于其的
        int begin = 0;
        int end = nums.size() - 1;
        int results = 0;
        while (begin <= end) {
            int mid = begin + end >> 1;
            if (nums.get(mid) >= value) {
                end = mid - 1;
            } else {
                begin = mid + 1;
                results = begin;
            }
        }
        return results;
    }


    public int lengthOfLIS1(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }

    // 动态规划实现
    public int lengthOfLIS2(int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i <= nums.length; i++) {
            int prevMax = 0;
            for (int j = i - 2; j >= 0; j--) {
                if (nums[j] < nums[i - 1]) {
                    prevMax = Math.max(dp[j + 1], prevMax);
                }
            }
            dp[i] = prevMax + 1;
            max = Math.max(dp[i], max);
        }
        return max;
    }

}
